package test230608;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/8 17:47
 * 647. 回文子串
 * https://leetcode.cn/problems/palindromic-substrings/
 */
public class Solution03 {

    // 动态规划法
    public int countSubstrings(String s) {
        // dp[i][j] 表示 s 字符串 [i, j] 的子串是否为回文串
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int ret = 0;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
                if (dp[i][j]) {
                    ++ret;
                }
            }
        }
        return ret;
    }

    // 中心扩展法
    public int countSubstrings2 (String s) {
        // 中心扩展法
        int ans = 0;
        int n = s.length();
        // 中心点可能有1个字符或者两个字符
        for (int center = 0; center < n; ++center) {
            // j = 0 时, 中心点一个字符, j = 1 时, 中心点两个字符
            for (int j = 0; j <= 1; j++) {
                int left = center;
                int right = center + j;
                while (left >= 0 && right < n && s.charAt(left--) == s.charAt(right++)) {
                    ++ans;
                }
            }
        }
        return ans;
    }
}
